package com.wtgroup.demo.面试题;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *
 * [最小体力消耗路径（算法） - 掘金](https://juejin.cn/post/7037370880611057701#heading-4)
 *
 * @author nisus
 * @version 0.1
 * @since 2023/6/1 12:13
 */
public class Q_最小体力消耗路径 {

    class Solution {
        int[] dis1=new int[]{1,-1,0,0};
        int[] dis2=new int[]{0,0,1,-1};
        PriorityQueue<Integer[]> queue;
        int max;
        boolean[][] array;
        int[][] heights;
        public int minimumEffortPath(int[][] heights) {
            queue=new PriorityQueue<>(new Comparator<Integer[]>() {
                @Override
                public int compare(Integer[] o1, Integer[] o2) {
                    return o1[0]-o2[0];
                }
            });
            max=0;
            this.heights=heights;
            int CN = heights[0].length;
            int RN = heights.length;
            array=new boolean[RN][CN];
            array[0][0]=true;
            if(array.length>1)queue.add(new Integer[]{Math.abs(heights[1][0]-heights[0][0]),1,0});
            if(array[0].length>1) queue.add(new Integer[]{Math.abs(heights[0][1]-heights[0][0]),0,1});

            while (queue.isEmpty()==false){
                Integer[] temp=queue.poll();
                max=Math.max(max,temp[0]);
                int curx=temp[1];
                int cury=temp[2];
                array[curx][cury]=true;
                if(curx==array.length-1 && cury==array[0].length-1)return max;
                for (int i = 0; i < dis1.length; i++) {
                    if(curx+dis1[i]>=0 && curx+dis1[i] < RN && cury+dis2[i]>=0 && cury+dis2[i] < CN){
                        if(array[curx+dis1[i]][cury+dis2[i]])continue;
                        queue.add(new Integer[]{Math.abs(heights[curx][cury]-heights[curx+dis1[i]][cury+dis2[i]]),curx+dis1[i],cury+dis2[i]});
                    }
                }
            }
            return 0;
        }

    }


}
